package com.xinwei.leetcode.数组;

import java.awt.datatransfer.FlavorListener;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;

// https://leetcode-cn.com/problems/insert-interval/
public class _57_插入区间 {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int len = intervals.length;
        int lefti = 0;
        for (int i = 0; i < len; i++) {
            if (newInterval[1] < intervals[i][1]){
                lefti = i - 1;
                break;
            }
        }
        int left = 0;
        if (newInterval[1] < intervals[lefti][2]) {
            left = intervals[lefti][1];
        }
        return null;
    }

    public int[][] insert1(int[][] intervals, int[] newInterval) {
        int[][] nums = new int[intervals.length + 1][2];
        nums[0] = newInterval;
        for (int i = 1; i < nums.length; i++) {
            nums[i] = intervals[i - 1];
        }
        Arrays.sort(nums, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
        ArrayList<int[]> lists = new ArrayList<>();
        lists.add(nums[0]);
        int[] prev = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i][0] > prev[1]) {
                // 正常分隔
                lists.add(nums[i]);
                prev = nums[i];
            }else { // nums[i][0] <= prev[1]
                // 有重合的部分，需要合并区间
                int right = Math.max(nums[i][1], nums[i - 1][i]);

                while (i < nums.length - 1 && right >= nums[i + 1][0]) {
                    if (right <= nums[i + 1][1]) {
                        right = nums[++i][1];
                    }else{
                        i++;
                    }
                }
                if (i == nums.length - 1) {
                    // 已经是最后一个
                    right = Math.max(nums[i][1], right);
                }else if (right < nums[i + 1][0]){
                    right = nums[i][1];
                }
                int[] ints = lists.get(lists.size() - 1);
                ints[1] = right;
                lists.set(lists.size() - 1, ints);
            }
        }
        return lists.toArray(new int[lists.size()][2]);
    }
}
